import java.util.HashSet;

public class HashBuck {
    //模拟实现一个hash桶
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    //创建一个数组,数组里面存放的是节点
    public Node[] array=new Node[10];

  //记录节点个数
    public int usedSize;
    //默认调节负载因子是0.75，一旦超过0.75就扩容
    public static final float DEFAULT_FACTOR=0.75f;

    //往哈希桶里面添加值为key的节点
    public void push(int key,int val) {
        int index=key%array.length;
        Node node=new Node(key,val);
        //找该index下标存放的链表中是否有为key的节点
        //如果有就更行val值即可
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }else{
                cur=cur.next;
            }
        }
        //走到这里就说明没有找到key的节点，采用头插法
        node.next=array[index];
        array[index]=node;
        this.usedSize++;
        if(doLoadFactor()>DEFAULT_FACTOR){
            resize();
        }
    }

    private void resize() {
        Node[] newarray=new Node[2*array.length];
        for(int i=0;i<array.length;i++){
            Node cur=array[i];
            while(cur!=null){
                Node curN=cur.next;
                int newindex=cur.val%newarray.length;
                cur.next=newarray[newindex];
                newarray[newindex]=cur;
                cur=curN;
            }
        }
        //最后让array指向newarray
        array=newarray;
    }

    private double doLoadFactor() {
        return usedSize*1.0 / array.length;
    }
    public int getVal(int key) {
        int index=key%array.length;
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.key;
            }
            cur=cur.next;
        }
        return  -1;
    }

}
